package outils.chemin;

import java.awt.Point;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import modele.Plateau;
import modele.case_.Case;
import modele.pion.Pion;

/**
 *
 * @author nicolas
 */
public class Dijkstra {

	private HashMap<Case, Double> cases;
	private HashMap<Case, Case> precedentes;

	/**
	 * Cherche les plus courts chemins parcourables par un pion
	 *
	 * @param pion
	 * @param plateau
	 */
	public Dijkstra(Pion pion, Plateau plateau) {
		cases = new HashMap<Case, Double>();
		precedentes = new HashMap<Case, Case>();
		plusCourtsChemins(pion, plateau);
	}

	/**
	 *
	 * @param pion le pion duquel on commence le parcours
	 * @param p le plateau de jeu
	 * @return les cases ainsi que le distance sur lesquelles le pion peut se
	 * rendre
	 */
	private void plusCourtsChemins(Pion pion, Plateau p) {
		Double distanceMax = pion.getRayon() + 1;
		Fap<Case, Double> fap = new Fap<Case, Double>();
		fap.inserer(pion.getCase(), 0d);

		cases.put(pion.getCase(), 0d);

		while (!fap.estVide()) {
			PairePoidsValeur<Case, Double> ppv = fap.extraire();
			Case c1 = ppv.valeur;
			ArrayList<Case> voisins = casesVoisines(pion, p, c1);
			for (Case c : voisins) {
				double dist = cases.get(c1) + Math.sqrt((c1.getX() - c.getX()) * (c1.getX() - c.getX()) + (c1.getY() - c.getY()) * (c1.getY() - c.getY()));
				if (dist <= distanceMax) {
					Double distancePrecedente = cases.get(c);
					if (distancePrecedente == null || dist < distancePrecedente) {
						cases.put(c, dist);
						precedentes.put(c, c1);
						fap.inserer(c, dist);
					}
				}
			}
		}

		ArrayList<Case> casesASupprimer = new ArrayList<Case>();
		for (Map.Entry<Case, Double> caseDistance : cases.entrySet()) {
			Case c = caseDistance.getKey();
			if (c.getPion() != null) {
				casesASupprimer.add(c);
			}
		}
		for (Case c : casesASupprimer) {
			cases.remove(c);
		}
	}

	/**
	 *
	 * @param pion le pion concerné
	 * @param p le plateau de jeu
	 * @param c la case dont on souhaite connaître les voisinnes
	 * @return les cases voisinnes de la case 'c' auxquelles peut accéder le
	 * pion 'pion'
	 */
	private ArrayList<Case> casesVoisines(Pion pion, Plateau p, Case c) {
		ArrayList<Case> casesVoisines = new ArrayList<Case>();
		Point coord = c.getCoord();
		int x = coord.x;
		int y = coord.y;

		Case voisines[] = {
			p.getCase(x - 1, y),
			p.getCase(x + 1, y),
			p.getCase(x, y - 1),
			p.getCase(x, y + 1),
			p.getCase(x - 1, y - 1),
			p.getCase(x + 1, y - 1),
			p.getCase(x - 1, y + 1),
			p.getCase(x + 1, y + 1)
		};
		for (Case c1 : voisines) {
			if (c1 != null && pion.peutAcceder(c1) && (c1.getPion() == null || pion.peutTraverser(c1.getPion()) || c1.getPion().peutTraverser(pion))) {
				casesVoisines.add(c1);
			}
		}

		return casesVoisines;
	}

	/**
	 *
	 * @param destination
	 * @return les cases du chemin jusqu'à la case 'destination'
	 */
	public ArrayList<Case> getChemin(Case destination) {
		ArrayList<Case> chemin = new ArrayList<Case>();
		Case precedent = destination;
		while (precedent != null) {
			chemin.add(0, precedent);
			precedent = precedentes.get(precedent);
		}
		return chemin;
	}

	/**
	 *
	 * @return les cases accessibles
	 */
	public HashMap<Case, Double> getCasesAccessibles() {
		return cases;
	}
}
